The present invention relates to a method of searching for routes and more particularly to a route searching method used with a navigation apparatus for determining an optimal route leading to a chosen destination.
An on-vehicle navigation apparatus detects the position of the vehicle, reads map data around the vehicle position from a map storage medium such as a DVD, and depicts the map on a display screen with a vehicle position marker superimposed at the vehicle's location on the map. The map can be scrolled as the vehicle moves forward while the vehicle position mark is fixed in a specific position, such as the center of the screen, and the map surrounding the vehicle's position can be viewed at a glance. In such an on-vehicle navigation apparatus, a route searching function may be provided to search out a route to enable travel from a starting point to a destination. It can determine the route, for example, taking the shortest time or the shortest distance, and display the route on the screen, thereby providing the vehicle driver with a driving guide. In such a route guiding function, the particular route is displayed with a thick, colored line during the actual driving, so that it can be distinguished from the other roads, allowing the driver to reach the destination easily. As the methods for searching out the guided route, along which the vehicle travels, from road map data, there are known the Dijkstra method, the A* algorithm, and the like.
The user of a route-searching navigation apparatus is not only concerned with the quality of the route, but also with the time necessary to produce it. An ideal navigation apparatus would be capable of solving a routing problem with faster speed and better quality. However, the quality of the solution and the time required for the search are generally in an inverse relationship. Practically speaking, a solution which is close to the optimum solution, obtained quickly, is more useful than finding the best solution with a longer searching time. The Dijkstra method or the A* algorithm, two commonly known methods, are able to provide an optimum path, but the broad range of the search increases the time that it takes. When the starting point is distant from the destination or the road network is dense, the optimal route searching time becomes even longer, as the number of intersections and links has become larger.